package com.sise.Linked;

/**
 *      剑指 Offer 36. 二叉搜索树与双向链表
 *
 *      输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
 *
 *      1 <-> 2 <-> 3       （双向链表）
 */
public class _offer_36_treeToDoublyList {

    Node pre;
    Node head;
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        dfs(root);
        head.left = pre;            // 等内部的节点连接完后，就设置头尾节点
        pre.right = head;
        return head;
    }

    private void dfs(Node cur){
        if (cur == null) return;

        dfs(cur.left);              // 由于使用的是 中序遍历，如下
        if (pre != null) {
            pre.right = cur;        // 如果前一个节点不为空，那么就设置双向链表
        }else {
            head = cur;             // 如果 pre 为 null，说明此时到达了尾结点，那么就将 cur 就是头结点了，将其赋值给 head
        }
        cur.left = pre;
        pre = cur;                  // 设置当前节点为 pre，为下一层递归做准备
        dfs(cur.right);

    }
}
